﻿#define _CRT_SECURE_NO_WARNINGS 1






#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int fa[N];//双亲表示法所需的数组

//初始化并查集
void init()
{
	for (int i = 1;i <= n;i++)
		fa[i] = i;
}

//查询操作
int find(int x)
{
	//return fa[x] == x ? x : find(fa[x]);
	//优化后：(找根节点-路径压缩)
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

//合并操作
void un(int x, int y)//union是C++的关键字
{
	int fx = find(x);
	int fy = find(y);
	fa[fx] = fy;
}

//判断操作
bool issame(int x, int y)
{
	return find(x) == find(y);
}


int main()
{
	return 0;
}


//并查集查询根节点的最坏时间复杂度为 O(α(n)) ，是⼀个很⼩的常数。因此，并查集查询以及合并的效率近似可以看成 O(1)。
//反阿克曼函数，增长非常缓慢，可以认为可控制的n中最多不超过4